package leetcode_1000;

import java.util.Stack;

public class MaximumWidthRamp_962 {
	public static void main(String[] args) {
		MaximumWidthRamp_962 test=new MaximumWidthRamp_962();
		System.out.println(test.maxWidthRamp(new int[] {3,4,1,2}));
	}
	
	public int maxWidthRamp(int[] A) {
		if(A.length==0) return 0;
		int []stack=new int[A.length];	
		int max=0,top=-1;
		stack[++top]=0;
		for(int i=1;i<A.length;++i) {
			if(A[i]<A[stack[top]]) stack[++top]=i;//保证值是递减的
			else {
				int run=top;
				while(run>=0&&A[i]>=A[stack[run]]) 
					--run;
				max=Math.max(max, i-stack[run+1]);
			}
		}
		return max;
    }
	
	
	public int maxWidthRamp1(int[] A) {
		int max=0;
		for(int i=0;i<A.length-1;++i) {
			for(int j=A.length-1;j>i;--j) {
				if(A[i]<=A[j]) max=Math.max(max, j-i);
			}
		}
		return max;
    }
}
